SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Chudnovsky algorithm</title>

</head>

Chudnovsky algorithm

</h1>

</header>

The Chudnovsky algorithm is a fast method for calculating the digits of <a href="Pi" title="Pi">π</a>, based on <a href="Ramanujan" class="mw-redirect" title="Ramanujan">Ramanujan</a>'s <a href="List_of_formulae_involving_%CF%80#Efficient_infinite_series" title="List of formulae involving π">π formulae</a>. Published by the <a href="Chudnovsky_brothers" title="Chudnovsky brothers">Chudnovsky brothers</a> in 1988,<a href="#cite_note-1">[1]</a> it was used to calculate π to a billion decimal places.<a href="#cite_note-2">[2]</a>

It was used in the <a href="Chronology_of_computation_of_%CF%80" title="Chronology of computation of π">world record</a> calculations of 2.7 trillion digits of π in December 2009,<a href="#cite_note-3">[3]</a> 10 trillion digits in October 2011,<a href="#cite_note-4">[4]</a><a href="#cite_note-5">[5]</a> 22.4 trillion digits in November 2016,<a href="#cite_note-6">[6]</a> 31.4 trillion digits in September 2018–January 2019,<a href="#cite_note-7">[7]</a> 50 trillion digits on January 29, 2020,<a href="#cite_note-8">[8]</a> 62.8 trillion digits on August 14, 2021,<a href="#cite_note-9">[9]</a> 100 trillion digits on March 21, 2022,<a href="#cite_note-10">[10]</a> 105 trillion digits on March 14, 2024,<a href="#cite_note-11">[11]</a> and 202 trillion digits on June 28, 2024.<a href="#cite_note-12">[12]</a> Recently, the record was broken yet again on April 2nd 2025 with 300 trillion digits of pi.<a href="#cite_note-13">[13]</a><a href="#cite_note-14">[14]</a> This was done through the usage of the algorithm on <a href="Y-cruncher" title="Y-cruncher">y-cruncher</a>.

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The algorithm is based on the negated <a href="Heegner_number" title="Heegner number">Heegner number</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d=-163}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle d=-163}</annotation>

</semantics>

</math><img src="./1a409cc537aae46f0453b8e85f5120c1c2543b82.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:9.61ex; height:2.343ex;" alt="{\displaystyle d=-163}" loading="lazy">, the <a href="J-invariant" title="J-invariant">j-function</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j\left({\tfrac {1+i{\sqrt {-163}}}{2}}\right)=-640320^{3}}">

<mrow>

<mfrac>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mfrac>

</mstyle>

</mrow>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j\left({\tfrac {1+i{\sqrt {-163}}}{2}}\right)=-640320^{3}}</annotation>

</semantics>

</math><img src="./c06fee5f98b7b316a564eb63b168af17eaa7bc61.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; margin-left: -0.027ex; width:25.7ex; height:4.843ex;" alt="{\displaystyle j\left({\tfrac {1+i{\sqrt {-163}}}{2}}\right)=-640320^{3}}" loading="lazy">, and on the following rapidly convergent <a href="Generalized_hypergeometric_series" class="mw-redirect" title="Generalized hypergeometric series">generalized hypergeometric series</a>:<a href="#cite_note-baruah-15">[15]</a><math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}}">

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

<mrow>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {1}{\pi }}=12\sum _{k=0}^{\infty }{\frac {(-1)^{k}(6k)!(545140134k+13591409)}{(3k)!(k!)^{3}(640320)^{3k+3/2}}}}</annotation>

</semantics>

</math>

This identity is similar to some of <a href="Ramanujan" class="mw-redirect" title="Ramanujan">Ramanujan</a>'s formulas involving π,<a href="#cite_note-baruah-15">[15]</a> and is an example of a <a href="Ramanujan%E2%80%93Sato_series" title="Ramanujan–Sato series">Ramanujan–Sato series</a>.

The <a href="Time_complexity" title="Time complexity">time complexity</a> of the algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left(n(\log n)^{3}\right)}">

<mrow>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left(n(\log n)^{3}\right)}</annotation>

</semantics>

</math><img src="./6aff00b4c7f5c55d547f027df0bb3844ca961345.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:13.302ex; height:3.343ex;" alt="{\displaystyle O\left(n(\log n)^{3}\right)}" loading="lazy">, where n is the number of digits desired.<a href="#cite_note-16">[16]</a>

<div class="mw-heading mw-heading2"><h2 id="Optimizations">Optimizations</h2></div>

The optimization technique used for the world record computations is called <a href="Binary_splitting" title="Binary splitting">binary splitting</a>.<a href="#cite_note-17">[17]</a>

/* start https://en.wikipedia.org/ */

.mw-parser-output .portalbox{padding:0;margin:0.5em 0;display:table;box-sizing:border-box;max-width:175px;list-style:none}.mw-parser-output .portalborder{border:1px solid var(--border-color-base,#a2a9b1);padding:0.1em;background:var(--background-color-neutral-subtle,#f8f9fa)}.mw-parser-output .portalbox-entry{display:table-row;font-size:85%;line-height:110%;height:1.9em;font-style:italic;font-weight:bold}.mw-parser-output .portalbox-image{display:table-cell;padding:0.2em;vertical-align:middle;text-align:center}.mw-parser-output .portalbox-link{display:table-cell;padding:0.2em 0.2em 0.2em 0.3em;vertical-align:middle}@media(min-width:720px){.mw-parser-output .portalleft{margin:0.5em 1em 0.5em 0}.mw-parser-output .portalright{clear:right;float:right;margin:0.5em 0 0.5em 1em}}

/* end https://en.wikipedia.org/ */

</style>

<ul><li><a href="Bailey%E2%80%93Borwein%E2%80%93Plouffe_formula" title="Bailey–Borwein–Plouffe formula">Bailey–Borwein–Plouffe formula</a></li>

<li><a href="Borwein's_algorithm" title="Borwein's algorithm">Borwein's algorithm</a></li>

<li><a href="Approximations_of_%CF%80" title="Approximations of π">Approximations of π</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFChudnovskyChudnovsky1988" class="citation cs2">Chudnovsky, David; Chudnovsky, Gregory (1988), Approximation and complex multiplication according to Ramanujan, Ramanujan revisited: proceedings of the centenary conference</cite>

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <cite id="CITEREFWarsiDangerfieldFarndonGriffiths2019" class="citation book cs1">Warsi, Karl; Dangerfield, Jan; Farndon, John; Griffiths, Johny; Jackson, Tom; Patel, Mukul; Pope, Sue; Parker, Matt (2019). The Math Book: Big Ideas Simply Explained. New York: <a href="Dorling_Kindersley_Limited" class="mw-redirect" title="Dorling Kindersley Limited">Dorling Kindersley Limited</a>. p. 65. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-4654-8024-8</bdi>.</cite>

</li>

<li id="cite_note-3"><a href="#cite_ref-3">^</a> <cite id="CITEREFBaruahBerndtChan2009" class="citation journal cs1">Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009-08-01). <a rel="nofollow" class="external text" href="http://openurl.ingenta.com/content/xref?genre=article&issn=0002-9890&volume=116&issue=7&spage=567">"Ramanujan's Series for 1/π: A Survey"</a>. American Mathematical Monthly. 116 (7): 567–587. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4169%2F193009709X458555">10.4169/193009709X458555</a>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFYeeKondo2011" class="citation cs2">Yee, Alexander; Kondo, Shigeru (2011), 10 Trillion Digits of Pi: A Case Study of summing Hypergeometric Series to high precision on Multicore Systems, Technical Report, Computer Science Department, University of Illinois, <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<a rel="nofollow" class="external text" href="https://hdl.handle.net/2142%2F28348">2142/28348</a></cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFAron2012" class="citation cs2">Aron, Jacob (March 14, 2012), <a rel="nofollow" class="external text" href="https://www.newscientist.com/article/dn21589-constants-clash-on-pi-day.html">"Constants clash on pi day"</a>, <a href="New_Scientist" title="New Scientist">New Scientist</a></cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.numberworld.org/y-cruncher/records/2016_11_11_pi.txt">"22.4 Trillion Digits of Pi"</a>. www.numberworld.org.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.numberworld.org/blogs/2019_3_14_pi_record/">"Google Cloud Topples the Pi Record"</a>. www.numberworld.org/.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.numberworld.org/y-cruncher/news/2020.html#2020_1_29">"The Pi Record Returns to the Personal Computer"</a>. www.numberworld.org/.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.fhgr.ch/fachgebiete/angewandte-zukunftstechnologien/davis-zentrum/pi-challenge/#c15513">"Pi-Challenge - Weltrekordversuch der FH Graubünden - FH Graubünden"</a>. www.fhgr.ch. Retrieved 2021-08-17.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://cloud.google.com/blog/products/compute/calculating-100-trillion-digits-of-pi-on-google-cloud">"Calculating 100 trillion digits of pi on Google Cloud"</a>. cloud.google.com. Retrieved 2022-06-10.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite id="CITEREFYee2024" class="citation web cs1">Yee, Alexander J. (2024-03-14). <a rel="nofollow" class="external text" href="http://www.numberworld.org/y-cruncher/news/2024.html#2024_3_13">"Limping to a new Pi Record of 105 Trillion Digits"</a>. NumberWorld.org. Retrieved 2024-03-16.</cite>

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFRanous2024" class="citation web cs1">Ranous, Jordan (2024-06-28). <a rel="nofollow" class="external text" href="https://www.storagereview.com/news/storagereview-lab-breaks-pi-calculation-world-record-with-over-202-trillion-digits">"StorageReview Lab Breaks Pi Calculation World Record with Over 202 Trillion Digits"</a>. StorageReview.com. Retrieved 2024-07-20.</cite>

</li>

<li id="cite_note-13"><a href="#cite_ref-13">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.numberworld.org/y-cruncher/news/2025.html#2025_5_16">"News (2024)"</a>. www.numberworld.org. Retrieved 2025-05-16.</cite>

</li>

<li id="cite_note-14"><a href="#cite_ref-14">^</a> <cite id="CITEREFLinus_Tech_Tips2025" class="citation audio-visual cs1">Linus Tech Tips (2025-05-16). <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=BD-AJwqzWsU">This World Record took YEARS (and a Million dollars..)</a>. Retrieved 2025-05-16 – via YouTube.</cite>

</li>

<li id="cite_note-baruah-15">^ <a href="#cite_ref-baruah_15-0">a</a> <a href="#cite_ref-baruah_15-1">b</a> <cite id="CITEREFBaruahBerndtChan2009" class="citation cs2">Baruah, Nayandeep Deka; Berndt, Bruce C.; Chan, Heng Huat (2009), "Ramanujan's series for 1/π: a survey", American Mathematical Monthly, 116 (7): 567–587, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.4169%2F193009709X458555">10.4169/193009709X458555</a>, <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/40391165">40391165</a>, <a href="MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=2549375">2549375</a></cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://www.numberworld.org/y-cruncher/internals/formulas.html">"y-cruncher - Formulas"</a>. www.numberworld.org. Retrieved 2018-02-25.</cite>

</li>

<cite id="CITEREFBrentZimmermann2010" class="citation book cs1"><a href="Richard_P._Brent" title="Richard P. Brent">Brent, Richard P.</a>; <a href="Paul_Zimmermann_(mathematician)" title="Paul Zimmermann (mathematician)">Zimmermann, Paul</a> (2010). Modern Computer Arithmetic. Vol. 18. <a href="Cambridge_University_Press" title="Cambridge University Press">Cambridge University Press</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1017%2FCBO9780511921698">10.1017/CBO9780511921698</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-511-92169-8</bdi>.</cite>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-29" href="https://en.wikipedia.org/wiki/?title=Chudnovsky_algorithm&oldid=1303194698">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>